package com.classicInterview;

/**
 * 判断一个括号字符串有效  (())有效，()(无效
 * <p>
 * 问题一：判断一个括号字符串有效
 * 问题二：最少需要填几个括号才使整个字符串有效
 * 问题三：返回括号字符串，最长括号字串的长度
 *
 * @Author: huangzhigao
 * @Date: 2022/2/12 9:37
 */
public class Code2_NeedParentheses {
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        for (char c : chars) {
            count += c == '(' ? 1 : -1;
            if (count < 0) {
                return false;
            }
        }

        return count == 0;
    }


    public int needParentheses(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        int need = 0;
        for (char c : chars) {
            count += c == '(' ? 1 : -1;
            if (count < 0) {
                //右括号多了，添加一个左括号，need++,同时count恢复成0；
                need++;
                count = 0;
            }
        }

        return need + count;
    }


    /**
     * 问题三：返回括号字符串，最长括号字串的长度
     * dp思想：
     * 如果i位置为(，dp[i]为0
     *
     * @param s
     * @return
     */
    public int MaxLength(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }
        char[] chars = s.toCharArray();
        //记录以i结尾的有效括号子串
        int[] dp = new int[s.length()];
        //以i-1结尾有效括号的上一个位置
        int pre = 0;
        int res = 0;
        //dp[0]一定为0，因为以第0个字符，没法直接构成有效字符
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == ')') {
                //查看当前位置与以i-1结尾有效括号的上一个位置,与当前字符配对的位置
                pre = i - dp[i - 1] - 1;
                if (pre >= 0 && chars[pre] == '(') {
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
            }

            //如果当前字符为(，则dp一定为0
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    public int maxDepth(String s) {
        if (!isValid(s)) {
            return 0;
        }

        int res = 0;
        int count = 0;
        char[] chars = s.toCharArray();
        for (char c : chars) {
            count += c == '(' ? 1 : -1;
            res = Math.max(count, res);
        }
        return res;
    }
}
